Search for: All records

Abstract Given a multigraph$$G=(V,E)$$, the edge-coloring problem (ECP) is to color the edges ofGwith the minimum number of colors so that no two adjacent edges have the same color. This problem can be naturally formulated as an integer program, and its linear programming relaxation is referred to as the fractional edge-coloring problem (FECP). The optimal value of ECP (resp. FECP) is called the chromatic index (resp. fractional chromatic index) ofG, denoted by$$\chi '(G)$$(resp.$$\chi ^*(G)$$). Let$$\Delta (G)$$be the maximum degree ofGand let$$\Gamma (G)$$be the density ofG, defined by$$\begin{aligned} \Gamma (G)=\max \left\{ \frac{2|E(U)|}{|U|-1}:\,\, U \subseteq V, \,\, |U|\ge 3 \hspace{5.69054pt}\textrm{and} \hspace{5.69054pt}\textrm{odd} \right\} , \end{aligned}$$whereE(U) is the set of all edges ofGwith both ends inU. Clearly,$$\max \{\Delta (G), \, \lceil \Gamma (G) \rceil \}$$is a lower bound for$$\chi '(G)$$. As shown by Seymour,$$\chi ^*(G)=\max \{\Delta (G), \, \Gamma (G)\}$$. In the early 1970s Goldberg and Seymour independently conjectured that$$\chi '(G) \le \max \{\Delta (G)+1, \, \lceil \Gamma (G) \rceil \}$$. Over the past five decades this conjecture, a cornerstone in modern edge-coloring, has been a subject of extensive research, and has stimulated an important body of work. In this paper we present a proof of this conjecture. Our result implies that, first, there are only two possible values for$$\chi '(G)$$, so an analogue to Vizing’s theorem on edge-colorings of simple graphs holds for multigraphs; second, although it isNP-hard in general to determine$$\chi '(G)$$, we can approximate it within one of its true value, and find it exactly in polynomial time when$$\Gamma (G)>\Delta (G)$$; third, every multigraphGsatisfies$$\chi '(G)-\chi ^*(G) \le 1$$, and thus FECP has a fascinating integer rounding property. 

ABSTRACT A subgraph of a graph with maximum degree is ‐overfullif . Clearly, if contains a ‐overfull subgraph, then its chromatic index is . However, the converse is not true, as demonstrated by the Petersen graph. Nevertheless, three families of graphs are conjectured to satisfy the converse statement: (1) graphs with (the Overfull Conjecture of Chetwynd and Hilton), (2) planar graphs (Seymour's Exact Conjecture), and (3) graphs whose subgraph induced on the set of maximum degree vertices is the union of vertex‐disjoint cycles (the Core Conjecture of Hilton and Zhao). Over the past decades, these conjectures have been central to the study of edge coloring in simple graphs. Progress had been slow until recently, when the Core Conjecture was confirmed by the authors in 2024. This breakthrough was achieved by extending Vizing's classical fan technique to two larger families of trees: the pseudo‐multifan and the lollipop. This paper investigates the properties of these two structures, forming part of the theoretical foundation used to prove the Core Conjecture. We anticipate that these developments will provide insights into verifying the Overfull Conjecture for graphs where the subgraph induced by maximum‐degree vertices has relatively small maximum degree. 

Abstract Themean subtree orderof a given graph , denoted , is the average number of vertices in a subtree of . Let be a connected graph. Chin et al. conjectured that if is a proper spanning supergraph of , then . Cameron and Mol disproved this conjecture by showing that there are infinitely many pairs of graphs and with , and such that . They also conjectured that for every positive integer , there exists a pair of graphs and with , , and such that . Furthermore, they proposed that provided . In this note, we confirm these two conjectures. 

Abstract Let be a simple graph and be the chromatic index of . We call a ‐critical graphif for every edge of , where is maximum degree of . Let be an edge of ‐critical graph and be an (proper) edge ‐coloring of . Ane‐fanis a sequence of alternating vertices and distinct edges such that edge is incident with or , is another endvertex of and is missing at a vertex before for each with . In this paper, we prove that if , where and denote the degrees of vertices and , respectively, then colors missing at different vertices of are distinct. Clearly, a Vizing fan is an ‐fan with the restricting that all edges being incident with one fixed endvertex of edge . This result gives a common generalization of several recently developed new results on multifan, double fan, Kierstead path of four vertices, and broom. By treating some colors of edges incident with vertices of low degrees as missing colors, Kostochka and Stiebitz introduced ‐fan. In this paper, we also generalize the ‐fan from centered at one vertex to one edge.